Disk storage is the primary storage medium for most systems. Systems operate in real time 24×7. Loss of data on a disk drive can cause the system to fail and may have significant non-recoverable impact on the functions supported by the system. Disk drive failures were the primary cause of loss of data. Ouchi, U.S. Pat. No. 4,092,732, disclosed recovery of data from N storage units and a redundant storage unit such that if any one of the storage units fail, the data on the failed storage unit can be reconstructed from the remaining N−1 storage units and the redundant storage unit. The data in the storage units are divided into addressable blocks. FIG. 1 illustrates data block D1 stored on storage unit U1, data block D2 stored on storage unit U2, etc. The redundant block R1 is derived from D1, D2, D3, D4, D5, and D6 such that a block can be reconstructed from the remaining N−1 blocks and the redundant block. The redundant block R1 is stored on storage unit 7. The set of blocks: D1, D2 D3, D4, D5, D6, and R1 is called a stripe. A stripe is updated by generating R1 for the stripe and writing all of the blocks.
A data block is updated by                1. Reading the old data block on the storage unit with the data block,        2. Reading the redundant block on the storage unit with redundant block,        3. Removing the effect of the old data block from the redundant block and adding the effect of the new data block to the redundant block        4. Writing the updated redundant block on the storage unit with the redundant block        5. Writing the new data block on the storage unit with the data block.        
For disk drive storage units, a data block update requires two disk drive reads and two disk drive writes and the two disk drives are busy (not available for other operations) for the duration of the operations. Many innovative people have worked to speed-up, hide, or otherwise try to minimize the impact of these disk drive reads and writes. However, two reads and two writes are required to update a data block.
While the probability of the loss of a disk drive is small, there is concern that there may be the loss of a second disk drive while the storage system is recovering from the loss of the first disk drive. Blaum, et al, U.S. Pat. No. 5,271,012, disclosed the use of multiple parity domains to protect against the loss of a second disk drive by providing for the reconstruction of two blocks. Blaum and Ouchi, U.S. Pat. No. 5,333,143, disclosed the use of an algebraic code called b-adjacent code from Patel, U.S. Pat. No. 3,745,528, to protect against the loss of a second disk drive. The b-adjacent code generates two redundant blocks from N data blocks to protect against two block failures within a stripe. The two redundant blocks are stored on an N+1th disk drive and an N+2th disk drive. FIG. 2 illustrates data block D1 stored on storage unit U1, etc. Redundant block R1 and redundant block R2 are derived from data blocks D1, D2, etc. Redundant block R1 is stored on storage unit U7 and redundant block R2 is stored on storage unit U8.
A data block update requires three disk drive reads and three disk drive write operations and the three disk drives are busy There are the four operations for the single block protection plus the read and write operations on the second redundant disk drive to process the second redundant block. The b-adjacent code can be constructed to protect against any given number of block failures; a redundant block is required for each block failure to be protected. For example, four-block failures can be protected with the generation of four redundant blocks; five-block failures can be protected with the generation of five redundant blocks, etc. However, to update a data block with four-block failure protection with the redundant blocks stored on four disk drives requires five read operations and five write operations and five busy disk drives.
Another mechanism to protect against loss of a block or storage unit is “mirroring”, duplicate images of the data blocks. FIG. 3 illustrates a mirrored storage array for data blocks D1, D2, D3, D4, D5, and D6. Data block D1 is stored on storage units U1 and U7, D2 on U2 and U8, etc. Mirroring provides for recovery from the loss of one storage unit and many combinations of loss of multiple storage units. In fact, half of the storage units can fail as long as two do not store the same data block. For example, storage units U7, U8, U9, U10, U11, and U12 can fail and the storage system still can access all data blocks. However, loss of U1 and U7 loses D1 and disables the storage system. Mirroring protects against all single storage unit failures and most double storage unit failures. Data block update only requires two writes, one each on the two storage units with the data block storage.
A variation on mirroring is the use of two duplicate images each with single block protection as illustrated in FIG. 4. Data block D1 is stored on storage units U1 and U8, etc. The redundant block R1 is generated from data blocks D1, D2, D3, D4, D5, and D6 and stored on storage units U7 and U14. Mirroring with single block protection provides for the loss of two drives that hold the same data block as long as the other storage units in a stripe are still operational. For example, storage units U7, U8, U9, U10, U11, U12, U13 and U14 can fail and storage unit U1 fail and the storage system is still operational. However, loss of any of two pairs (U1, U8) (U2, U9) (U3, U10) (U4, U11) (U5, U12) (U6, U13) or (U7, U14) will disable the storage system. Mirroring with single block protection protects against all combinations of three storage unit failures and most four storage unit failures. A data block update requires two sets of two read operations and two write operations.
Mirroring requires N additional storage units to protect N storage units. Mirroring with single block protection requires N+2 storage units to protect N storage units. Algebraic codes such as the b-adjacent code provide protection by adding storage for one block per block failure protected independent of the number of storage units, N. That is, one unit is added to protect against single unit failures, two units added to protect against two unit failures, etc. In spite of rapidly decreasing disk drive costs, most storage system users do not want to double the storage system capacity for mirroring except for very demanding performance requirements or small storage systems. For some storage systems, the high performance mirrored information is shadow copied to storage protected with algebraic code redundancy. Mirroring with single block protection provides significant protection. However, the number of redundant units is high compared to the units protected and the data block update overhead is equivalent to the single block protection without mirroring. The algebraic codes provide very efficient protection with a significantly smaller number of added storage units. However, the data block update overhead increases by two accesses for each additional block failure protection. Mirroring faces the same problem as a higher number block failures are protected since the added protection is provided by algebraic codes. Only the most demanding performance and availability applications can afford triple mirroring.
It is desirable to provide data protection afforded by algebraic codes for failures that do not cause the loss of a storage unit without the growth in data block update overhead as block protection is added.